package com.fw.structure.tree.huffmantree;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
import lombok.ToString;

import javax.xml.soap.Node;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * huffmantree 树的创建过程
 */
public class HuffManTreeDemo {

    public static void main(String[] args) {
        int[] arr = {8,16,9,32,14,16};
        perLists(createHuffManTree(arr));
    }

    /**
     * 创建 huffManTree
     */
    public static NodeTree createHuffManTree(int[] arr){
        List<NodeTree> nodeTreeList = new ArrayList<>();
        for (int i : arr) {
            nodeTreeList.add(new NodeTree(i));
        }
        while (nodeTreeList.size() > 1){
            // 1. 从小到大进行排序,将每一个数据，每个数据都是一个节点，每个节点可以看成是一颗最简单的二叉树
            Collections.sort(nodeTreeList);
            // 2. 取出根节点权值最小的两颗二叉树
            NodeTree nodeTreeMin = nodeTreeList.get(0);
            NodeTree nodeTreeMin2 = nodeTreeList.get(1);
            //3. 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
            NodeTree parentNodeTree = new NodeTree(nodeTreeMin.getVal() + nodeTreeMin2.getVal());
            parentNodeTree.setLeftNode(nodeTreeMin);
            parentNodeTree.setRightNode(nodeTreeMin2);
            nodeTreeList.remove(nodeTreeMin);
            nodeTreeList.remove(nodeTreeMin2);
            nodeTreeList.add(parentNodeTree);
            //4. 再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4
        }
        return nodeTreeList.get(0);
    }

    /**
     * 前序遍历
     */
    public static void perLists(NodeTree nodeTree){
        System.out.println(nodeTree.getVal());
        if (nodeTree.getLeftNode() != null)
            perLists(nodeTree.getLeftNode());
        if (nodeTree.getRightNode() != null)
            perLists(nodeTree.getRightNode());
    }
}

@Data
@ToString
@NoArgsConstructor
class NodeTree implements Comparable<NodeTree>{

    private int val;

    public NodeTree(int val) {
        this.val = val;
    }

    @ToString.Exclude
    private NodeTree leftNode;
    @ToString.Exclude
    private NodeTree rightNode;


    /**
     * 进行排序
     * @param o
     * @return
     */
    @Override
    public int compareTo(NodeTree o) {
        return this.val - o.val;
    }
}
